/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 构造一个虚拟头节点指向链表
        ListNode* newhead = new ListNode(0);
        newhead->next = head;

        // 初始化双指针
        ListNode* p = newhead;
        ListNode* q = newhead;

        // 让 p 先走 n+1 步
        for (int i = 0; i <= n; i++) {
            if (p == nullptr) {
                // 如果链表长度不足 n+1，直接返回原链表
                delete newhead;
                return head;
            }
            p = p->next;
        }

        // 双指针等距移动，直到 p 指向 nullptr
        while (p != nullptr) {
            p = p->next;
            q = q->next;
        }

        // 删除倒数第 n 个节点
        q->next = q->next->next;

        // 返回新的头节点
        ListNode* result = newhead->next;
        delete newhead; // 释放虚拟头节点内存
        return result;
    }
};